package day15;

public class Algorithm03 {
    public static void main(String[] args) {                //快速排序
        int[] arr = {6,1,2,5,4,3,9,7,10,8};
        quicksort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static void quicksort(int[] arr, int left, int right) {
        if (left >= right) return;

        int pivot = arr[left];
        int i = left;
        int j = right;

        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            while (i < j && arr[i] <= pivot) i++;
            if (i < j) {
                swap(arr, i, j);
            }
        }
        swap(arr, left, i);
        quicksort(arr, left, i - 1);
        quicksort(arr, i + 1, right);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
